package DataStructureAndAlgorithm.CSP.Day13;

import java.util.*;

class AcWing_3255{

    static class Node implements Comparable<Node>{
        int x,y,v;
        Node(int x,int y,int v){
            this.x = x;
            this.y = y;
            this.v = v;
        }
        //自定义比较函数，实现小根堆
        @Override
        public int compareTo(Node temp){
            return this.v - temp.v;
        }
    }

    static int N = 510,M = 200010,INF = 1000010;
    static int n,m;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] f = new int[M];
    static int[] w = new int[M];
    static int[] ne = new int[M];
    static int idx= 0;
    //拆点技巧，当一个点有多种状态也不容易求时，
    //可以把一个点的不同状态看成是不同的点来分别求解
    //dist[i][j]：表示从起点走到i点时，小路的长度为j
    static int[][] dist = new int[N][1010];
    //判重数组，用于判断点是否已经走过
    static boolean[][] st = new boolean[N][1010];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++){
            int t = in.nextInt();
            int a = in.nextInt();
            int b = in.nextInt();
            int c = in.nextInt();
            //建立无向图
            add(t,a,b,c);
            add(t,b,a,c);
        }

        dijkstra();
        //在所有从起点走到n点，最后经过的下路的长度为j所有长度中求出最小的值，即为答案
        int res = INF;
        for (int i = 0; i <= 1000; i++){
            res = Math.min(res,dist[n][i]);
        }

        System.out.println(res);

    }

    static void add(int t,int a,int b,int c){
        e[idx] = b;
        f[idx] = t;//f表示状态
        w[idx] = c;//w表示权重
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void dijkstra(){
        //dijkstra优化版需要用到优先队列，此处为小根堆
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(1,0,0));
        //初始化所有的距离为无穷大
        for (int i = 0; i < N; i++){
            Arrays.fill(dist[i],Integer.MAX_VALUE);
        }
        dist[1][0] = 0;
        while (!queue.isEmpty()){
            Node temp = queue.poll();
            //判断点[temp.x][temp.y]是否已经走过
            if (st[temp.x][temp.y])continue;
            st[temp.x][temp.y] = true;
            //遍历点[][]的所有邻点
            for (int i = h[temp.x]; i != -1; i = ne[i]){
                int x = e[i];
                int y = temp.y;
                //如果是小路
                if (f[i] != 0){
                    y += w[i];
                    //有答案小于1e6,因此，y必然要小于1000
                    if (y <= 1000){
                        //判断更新
                        if (dist[x][y] > temp.v - temp.y * temp.y + y * y){
                            dist[x][y] = temp.v - temp.y * temp.y + y * y;
                            //如果到达点的距离没有超过最大值，则还可以往下走，
                            //因此，将当前点加入堆中，用于继续计算
                            if (dist[x][y] <= INF){
                                queue.offer(new Node(x,y,dist[x][y]));
                            }
                        }
                    }
                }else {
                    //如果是大路
                    //判断更新
                    if (dist[x][0] > temp.v + w[i]){
                        dist[x][0] = temp.v + w[i];
                        //如果到达点的距离没有超过最大值，则还可以往下走，
                        //因此，将当前点加入堆中，用于继续计算
                        if (dist[x][0] <= INF){
                            queue.offer(new Node(x,0,dist[x][0]));
                        }
                    }
                }
            }
        }
    }
}
